class Solution {
    public:
        bool wordBreak(string s, vector<string>& wordDict) {
            unordered_set<string> se;
            for(auto& x:wordDict)   se.insert(x);
            int n = s.size();
            vector<bool> dp(n+1);//dp[i]表示以i-1位置为结尾的单词是否能在字典中找出
            dp[0]=true;
            //if(se.count(s.substr(0,1)))   dp[1] = true;
            for(int i = 0 ; i < n ; i++){
                for(int j = 0 ; j <= i ; j++){
                    string sub = s.substr(j,i-j+1);
                    //cout<<sub<<endl;
                    if(dp[j] && se.count(sub)){
                        dp[i+1] = true;
                        break;
                    }
                }
            }
            return dp[n];
        }
    };